package com.dragon.datastructure.linkedlist;


/**
 * 约瑟夫环单链表解法
 *
 * @author dragon
 * @since 2019/12/20
 */
public class Test7 {

    private static class Node {
        int item;
        Node next;

        public Node(int item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        int luckyNumber = getLuckyNumber(5, 1, 2);
        System.out.println(luckyNumber);
    }

    /**
     * 得到幸运数字
     *
     * @param totalNumber 总人数
     * @param startNumber 从几号开始
     * @param count       数到count次之后的这个人就出列
     * @return 返回最后一个幸运数字
     */
    public static int getLuckyNumber(int totalNumber, int startNumber, int count) {
        if (totalNumber <= 0 || totalNumber < startNumber || startNumber < 1 || count < 0) {
            throw new IllegalArgumentException("参数有误");
        }
        // 返回单链表的前驱节点
        Node pre = createSingleLoopLinkedList(totalNumber);
        // 定义头节点
        Node cur = pre.next;
        // 1.找到当前开始的节点
        for (int i = 1; i < startNumber; i++) {
            cur = cur.next;
        }
        // 定义点到的次数
        int countedNum = 1;
        while (cur.next != cur) {
            // 已经点到的次数达到了
            if (countedNum == count) {
                countedNum = 1;
                pre.next = cur.next;
                System.out.println("被杀的人的号码:" + cur.item);
                cur.next = null;
                cur = pre.next;
            } else {
                countedNum++;
                pre = cur;
                cur = cur.next;
            }
        }

        return cur.item;
    }

    /**
     * 创建单链表
     *
     * @param totalNumber 链表元素个数
     * @return 返回环形单链表的头节点的前驱节点
     */
    public static Node createSingleLoopLinkedList(int totalNumber) {
        Node head = new Node(1, null);
        head.next = head;
        Node prevNode = head;
        for (int i = 2; i <= totalNumber; i++) {
            Node node = new Node(i, null);
            prevNode.next = node;
            prevNode = node;
        }
        prevNode.next = head;

        return prevNode;
    }
}
